package com.example.rwq_test.niuke.tree;

/**
 * 转变为有序双向链表
 *
 * @author renweiqiang
 * @version 1.0.0
 * @createTime 2023/11/21
 */
public class BinaryTreeToDoubleList {
    public static TreeNode head;
    public static TreeNode cur;

    /**
     * 转变为有序双向链表
     *
     * @param root
     * @return
     */
    public static TreeNode convert(TreeNode root) {
        if (root == null) {
            return null;
        }
        convert(root.left);
        if (head == null) {
            head = root;
            cur = root;
        } else {
            cur.right = root;
            root.left = cur;
            cur = root;
        }
        convert(root.right);
        return head;
    }

    public static void main(String[] args) {
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode0 = new TreeNode(0);
        TreeNode treeNode8 = new TreeNode(8);
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode4 = new TreeNode(4);

        treeNode3.left = treeNode5;
        treeNode3.right = treeNode1;
        treeNode5.left = treeNode6;
        treeNode5.right = treeNode2;
        treeNode1.left = treeNode0;
        treeNode1.right = treeNode8;
        treeNode2.left = treeNode7;
        treeNode2.right = treeNode4;
        TreeNode convert = convert(treeNode3);
        System.out.println(convert);
    }
}
